package com.zdb.algorithm.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GreedyAlgorithm {

    public static void main(String[] args) {
        Map<String, Set<String>> broadcasts = new HashMap<>();

        Set<String> set1 = new HashSet<>();
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");
        Set<String> set2 = new HashSet<>();
        set2.add("广州");
        set2.add("北京");
        set2.add("深圳");
        Set<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("上海");
        set3.add("杭州");
        Set<String> set4 = new HashSet<>();
        set4.add("上海");
        set4.add("天津");
        Set<String> set5 = new HashSet<>();
        set5.add("杭州");
        set5.add("大连");

        broadcasts.put("k1", set1);
        broadcasts.put("k2", set2);
        broadcasts.put("k3", set3);
        broadcasts.put("k4", set4);
        broadcasts.put("k5", set5);

        Set<String> allAreas = new HashSet<>();

        for(Map.Entry<String, Set<String>> entry : broadcasts.entrySet()) {
            allAreas.addAll(entry.getValue());
        }

        System.out.println("需要覆盖的所有区域为：" + allAreas.size() + "，" + allAreas);

        // 选择的电台名集合
        List<String> selected = new ArrayList<>();

        String maxKey = null;
        int maxKeyNum = 0;
        while (allAreas.size() > 0) {

            maxKey = null;
            maxKeyNum = 0;

            // 先遍历所有电台，找出能覆盖allAreas中区域最多的电台
            for(Map.Entry<String, Set<String>> broadcast : broadcasts.entrySet()) {

                Set<String> areas = broadcast.getValue();
                int hasCnt = getContainCnt(allAreas, areas);

                if(hasCnt >maxKeyNum) {
                    maxKey = broadcast.getKey();
                    maxKeyNum = hasCnt;
                }

            }

            if(maxKey != null) {
                selected.add(maxKey);
                // 将需要覆盖的区域扣除掉已覆盖的
                allAreas.removeAll(broadcasts.get(maxKey));
            }

        }

        System.out.println("贪婪算法得到的电台：" + selected);

    }

    /**
     * 获取areas在 allAreas中的数量
     * @param allAreas
     * @param areas
     * @return
     */
    private static int getContainCnt(Set<String> allAreas, Set<String> areas) {

        int cnt = 0;

        for(String area : areas) {
            if(allAreas.contains(area)) {
                cnt++;
            }
        }

        return cnt;

    }
}
